package com.kingwood.algorithm.test;

import java.util.Arrays;
import java.util.Scanner;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

/**
 * @Author 22025812
 * @Description: 二分相关的经典题目
 * @Date: 2024/3/6 13:55
 * @Modified By：
 * @Version 1.0
 */
public class ErFen2 {

    static Pattern p = Pattern.compile("(<.*?>)");

    /**
     * 部门人力分配
     * https://fcqian.blog.csdn.net/article/details/134724995
     * @param m
     * @param requirements
     * @return
     */
    public static int getMinHumanResource(int m, int[] requirements) {
        int ans = 0;
        Arrays.sort(requirements);

        int len = requirements.length;
        int minHr = requirements[len - 1];
        int maxHr = minHr + requirements[len - 2];

        while (minHr <= maxHr) {
            int mid = (minHr + maxHr) / 2;
            if (checkHr(mid, m, requirements)) {
                ans = mid;
                maxHr = mid - 1;
            } else {
                minHr = mid + 1;
            }
        }

        return ans;
    }

    public static boolean checkHr(int hr, int m, int[] requirements) {
        int l = 0;
        int r = requirements.length - 1;

        int needHr = 0;
        while (l <= r) {
            if (requirements[l] + requirements[r] <= hr) {
                l++;
            }
            r--;
            needHr++;
        }

        return m >= needHr;
    }

    static int x;
    static int y;
    static long cntX;
    static long cntY;

    /**
     * 员工派遣
     * https://blog.csdn.net/qfc_128220/article/details/135050312
     * @return
     */
    public static long getMinYuanGong() {
        long min = cntX + cntY;
        long max = 1000000000L;

        while (min <= max) {
            long mid = min + (max - min) / 2;
            if (checkYuanGong(mid)) {
                max = mid - 1;
            } else {
                min = mid + 1;
            }
        }

        return min;
    }

    public static boolean checkYuanGong(long k) {
        long a = k / x;
        long b = k / y;
        long c = k / (x * y);

        return Math.max(0, cntX - (b - c)) + Math.max(0, cntY - (a - c)) <= k - a - b + c;
    }

    /**
     * 项目排期
     * https://fcqian.blog.csdn.net/article/details/134772481
     * @param arr
     * @param n
     * @return
     */
    public static int getProjectMinDays(int[] arr, int n) {
        int ans = 0;
        Arrays.sort(arr);
        int sum = Arrays.stream(arr).sum();
        int len = arr.length;
        int min = arr[len - 1];
        int max = sum;

        while (min <= max) {
            int mid = min + (max - min) / 2;
            if (checkProjectDays(sum, n, mid)) {
                ans = mid;
                max = mid - 1;
            } else {
                min = mid + 1;
            }
        }

        return ans;
    }

    public static boolean checkProjectDays(int sum, int n, int k) {
        if (n * k >= sum) {
            return true;
        }

        return false;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();
        scanner.nextLine();
        int[] requirements = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();

        int minHumanResource = getMinHumanResource(m, requirements);
        System.out.println(minHumanResource);

//        x = scanner.nextInt();
//        y = scanner.nextInt();
//        cntX = scanner.nextLong();
//        cntY = scanner.nextLong();
//
//        System.out.println(getMinYuanGong());

//        int[] arr = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
//        int n = scanner.nextInt();
//        System.out.println(getProjectMinDays(arr, n));
    }
}
